package com.zyk.leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author zhangsan
 * @date 2021/4/5 19:27
 */
public class M34 {

    List<List<Integer>> ans = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();

    // https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        recure(root, target);
        return ans;
    }

    private void recure(TreeNode head, int target) {
        if(head == null) {
            return;
        }
        // 前序遍历, 因为要先把自己的路径加上.才能做左树 右树
        path.add(head.val);
        target -= head.val;
        if(target == 0 && head.left == null && head.right == null) {
            // 到达了目标值,同时是个叶子节点是正确解
            ans.add(new ArrayList<>(path));
        }
        // 左树右树玩
        recure(head.left, target);
        recure(head.right, target);
        // 自己玩完, 把自己从path里删掉
        path.removeLast();
    }
}
